#include "stack_queue.h"
#include <iostream>


using namespace std;


//初始化链式栈 构造函数
MyStack::MyStack(){
    topNode = NULL;
    stackSize = 0;
}

//析构函数
MyStack::~MyStack(){
    while(topNode!= NULL){
        listNode* p = topNode;
        topNode = topNode->next;
        delete p;
    }
}

//入栈
bool MyStack::push(const int& nodeData){
    listNode* newNode = new listNode(nodeData,topNode);
    topNode=newNode;
    stackSize++;
    return true;
}

//op入栈 
bool MyStack::push(const char& item){
    listNode* newNode = new listNode(item,topNode);
    stackSize++;
    return true;
}

//出栈
bool MyStack::pop(int & item){
    if (topNode == NULL) return false;
    item = topNode->data;
    listNode* p = topNode;
    topNode = topNode->next;//更新topNode
    delete p;
    stackSize--;
    return true;
}

//op出栈
bool MyStack::pop(char & item){
    if (topNode == NULL) return false; // 检查栈是否为空
    item = topNode->op;
    listNode* p = topNode;
    topNode = topNode->next;//更新topNode
    delete p;
    stackSize--;
    return true;
}

//返回栈顶元素
bool MyStack::getTop(int & item){
    if(topNode ==NULL) return false;
    item = topNode->data;
    return true;
}

//返回栈顶op
bool MyStack::getTop(char & item){
    if(topNode ==NULL) return false;
    item = topNode->op;
    return true;
}


//打印链栈
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

//顺序循坏队列初始化
MyQueue::MyQueue(const int& MAXSIZE){
    capacity = MAXSIZE;
    front = rear = 0;
    queue = new int[capacity];
}

//析构函数
MyQueue::~MyQueue() {
    delete[] queue;
}

//入队
bool MyQueue::enQueue(const int& item){
    if((rear + 1) % capacity == front) return false; // 队列已满
    queue[rear] = item;
    rear = (rear +1)%capacity;
    return true;
}

//出队
bool MyQueue::deQueue(int& item){
    if(front == rear) return false; // 队列为空
    item = queue[front];
    front = (front +1)%capacity;
    return true;
}

//返回队首元素
bool MyQueue::getFront(int& item){
    if(front == rear) return false; // 队列为空
    item = queue[front];
    return true;
}

//打印顺序循环队列
void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

//判断栈是否为空
bool MyStack::isEmpty(){
    return stackSize == 0;
}

//判断队列是否满
bool MyQueue::isFull(){
    return (rear + 1) % capacity == front;
}


//操作符优先级
int priority(char op){
    if(op == '+' || op == '-') return 1;
    if(op == '*' || op == '/') return 2;
    return 0;
}


//中缀表达式转后缀表达式
bool postfixExpression(const string& infix, string& result) {
    MyStack opStack;
    for (int i = 0; i < infix.length(); i++) {
        char ch = infix[i];
        if (ch >= '0' && ch <= '9') {
            result += ch;//数字直接输出
        } else if (ch == '(') {
            opStack.push(ch);
        } else if (ch == ')') {
            char topOp;
            bool foundLeftParenthesis = false;//匹配括号
            while (!opStack.isEmpty() && opStack.getTop(topOp) && topOp!= '(') {
                opStack.pop(topOp);
                result += topOp;//输出匹配上符号的操作符
            }
            if (!opStack.isEmpty() && opStack.getTop(topOp) && topOp == '(') {
                opStack.pop(topOp);//匹配好的括号不输出
                foundLeftParenthesis = true;
            }
            if (!foundLeftParenthesis) {
                result= "Expression is wrong!" ; 
                return false;
            }
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            char topOp;
            while (!opStack.isEmpty() && opStack.getTop(topOp) && priority(topOp) >= priority(ch)) { // 栈顶操作符优先级大于当前操作符 出栈
                opStack.pop(topOp);
                result += topOp;
            }
            opStack.push(ch);
        }
    }
    while (!opStack.isEmpty()) {
        char topOp;
        if (opStack.getTop(topOp) && topOp == '(') { //有未匹配的左括号
            result= "Expression is wrong!" ; 
            return false;
        }
        opStack.pop(topOp);
        result += topOp;
    }
    return true;
}


// 计算中缀表达式的值
bool expressionVal(const string& infix, int& result) {
    MyStack OPND;
    MyStack OPTR;
   for (int i = 0; i < infix.length(); i++) {
        char ch = infix[i];
        if (ch >= '0' && ch <= '9') {
            OPND.push(ch - '0');
        } else if (ch == '(') {
            OPTR.push(ch);
        } else if (ch == ')') {
            char topOp;
            while (!OPTR.isEmpty() && OPTR.getTop(topOp) && topOp!= '(') {
                OPTR.pop(topOp);
                int operand2;
                OPND.pop(operand2);
                int operand1;
                OPND.pop(operand1);
                switch (topOp) {
                    case '+': OPND.push(operand1 + operand2); break;
                    case '-': OPND.push(operand1 - operand2); break;
                    case '*': OPND.push(operand1 * operand2); break;
                    case '/': OPND.push(operand1 / operand2); break;
                }
            }
            if (!OPTR.isEmpty() && OPTR.getTop(topOp) && topOp == '(') {
                OPTR.pop(topOp);
            }
        } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            char topOp;
            while (!OPTR.isEmpty() && OPTR.getTop(topOp) && priority(topOp) >= priority(ch)) {
                OPTR.pop(topOp);
                int operand2;
                OPND.pop(operand2);
                int operand1;
                OPND.pop(operand1);
                switch (topOp) {
                    case '+': OPND.push(operand1 + operand2); break;
                    case '-': OPND.push(operand1 - operand2); break;
                    case '*': OPND.push(operand1 * operand2); break;
                    case '/': OPND.push(operand1 / operand2); break;
                }
            }
            OPTR.push(ch);
        }
    }
    while (!OPTR.isEmpty()) {
        char topOp;
        OPTR.pop(topOp);
        int operand2;
        OPND.pop(operand2);
        int operand1;
        OPND.pop(operand1);
        switch (topOp) {
            case '+': OPND.push(operand1 + operand2); break;
            case '-': OPND.push(operand1 - operand2); break;
            case '*': OPND.push(operand1 * operand2); break;
            case '/': OPND.push(operand1 / operand2); break;
        }
    }
    OPND.pop(result);
    return true;
}



//杨辉三角
void yanghui(const int& n) {
    MyQueue q(n+2);//队列多存了n个零 j=1到i+2
    q.enQueue(1);
    q.enQueue(1);
    int s =0;
    for (int i = 1; i <= n; i++) {
        q.enQueue(0);
        for (int j = 1; j <= i + 2; j++){//i+2是为了遍历队列到0的位置
            int t;
            q.deQueue(t);
            q.enQueue(s+t);
            s=t;
            if(j!=i+2&&j!=i+1) cout << s << ",";
            if(j==i+1) cout<<s;//0前位置输出不用“，”
            }
            cout<<endl;
            }
}



